//给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
//
// 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
//
// 你可以认为每种硬币的数量是无限的。
//
//
//
// 示例 1：
//
//
//输入：coins = [1, 2, 5], amount = 11
//输出：3
//解释：11 = 5 + 5 + 1
//
// 示例 2：
//
//
//输入：coins = [2], amount = 3
//输出：-1
//
// 示例 3：
//
//
//输入：coins = [1], amount = 0
//输出：0
//
//
//
//
// 提示：
//
//
// 1 <= coins.length <= 12
// 1 <= coins[i] <= 2³¹ - 1
// 0 <= amount <= 10⁴
//
//
// Related Topics 广度优先搜索 数组与矩阵 动态规划 👍 2387 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function coinChange(coins: number[], amount: number): number {

    /*
    ? 1.确定dp数组以及下标的含义
    ? dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
    ? 2.确定递推公式
    ? 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]（不考虑coins[i]），那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
    ? 所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
    ? 递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
    ? 3.dp数组如何初始化
    ? 首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
    ? 其他下标对应的数值呢？
    ? 考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。
    ? 所以下标非0的元素都是应该是最大值。
     */

    const dp: number[] = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    //? 完全背包问题
    //? 物品
    for (let i = 0; i < coins.length; i++) {
        //? 背包
        for (let j = coins[i]; j <= amount; j++) {
            if (dp[j - coins[i]] === Infinity) continue;
            //? 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]](不考虑coins[i])，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
            //? 所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
            dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
};
//leetcode submit region end(Prohibit modification and deletion)
